package labuladong;

// 并查集算法
    /* Union-Find算法主要需要实现两个API
        class UF{
            // 将p和q连接
            public void union(int p, int q);
            // 判断p和q是否连通
            public boolean connected(int p, int q);
            // 返回有多少个连通分量
            public int count();
        }
        // 10个点，没有连通性时
        class UF{
            // 记录连通分量
            pirvate int count;
            // 节点x的节点是parent[x]
            private int[] parent
            // 构造函数， n为图的节点总数
            public UF(int n){
                this.count = n;
                parent = new int[n];
                for(int i=0;i<n;i++){
                    parent[i] = i;
                }
            }
        }
    */
public class UF {
    // 记录连通分量
    private int count;
    // 节点x的节点是parent[x]
    private int[] parent;
    // 构造函数。n为图的节点总数
    public UF(int n){
        this.count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            // 刚开始的父节点是自己
            parent[i] = i;
        }
    }
    public  void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return;
        }
        // 将两个树合并为一颗
        parent[rootP] = rootQ; // parent[rootQ] = rootP也行
        count--; // 连通分量减一
    }

    // 返回某个节点x的根节点,数组parent的x下标储存的是x的父节点
    private int find(int x){
        while(parent[x]!=x){
            x = parent[x];
        }
        return x;
    }

    // 返回连通分量的个数
    public int count(){
       
         return count;
    }

    // 一个简单的使用，判断合法算式
    /* 给你一个数组equations，装着若干字符串表示的算式。每个算式equations[i]长度都是 4，
       而且只有这两种情况：a==b或者a!=b，其中a,b可以是任意小写字母。你写一个算法，
       如果equations中所有算式都不会互相冲突，返回 true，否则返回 false。 */
    boolean equationsPossible(String[] equations){
        UFBest uf = new UFBest(26);
        for(String eq : equations){
            if(eq.charAt(1)=='='){
                char x = eq.charAt(0);
                char y = eq.charAt(3);
                uf.union(x-'a',y-'a');
            }
        }
        for(String eq : equations){
            if(eq.charAt(1)=='!'){
                char x = eq.charAt(0);
                char y = eq.charAt(3);
                if(uf.connected(x, y))
                    return false;
            }
        }
        return true;
    }
}


/* 维持一个平衡的树 */
class UFwithBalance{
    private int count;
    private int[] parent;
    // 新增一个数组记录树的重量
    private int[] size;
    public UFwithBalance(int n){
        this.count = n;
        parent =  new int[n];
        // 最初只有一个节点，重量初始化为1
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    public void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return;
        }
        if(size[rootP]>size[rootP]){
            parent[rootQ] = rootP;
            size[rootP]+=size[rootQ];
        }else{
            parent[rootP] = rootQ;
            size[rootQ]+=size[rootP];
        }
        count--;
    }
    // 返回某个节点x的根节点,数组parent的x下标储存的是x的父节点
    private int find(int x){
        while(parent[x]!=x){
            x = parent[x];
        }
        return x;
    }

    // 返回连通分量的个数
    public int count(){
        return count;
    }
}
class UFBest {
    // 连通分量个数
    private int count;
    // 存储一棵树
    private int[] parent;
    // 记录树的“重量”
    private int[] size;

    public UFBest(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;

        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }

    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    private int find(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}